package zuo.baseUP7_ForceRec;

import javafx.geometry.Pos;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author: Forx
 * @Data: 2021/6/20
 * @Desc: Algorithm - zuo.baseUP7_ForceRec
 * @Version: v1.0
 */
public class DPMutiTables {

    /**
     * 优化 test7中的先后手比赛问题
     *
     *
     * */
    /**
     * 在一个10*9的棋盘上,马的位置在(0,0),现在要求
     * 在K步的时候到达(a,b)的方法数
     *
     * 马跳日,因此总共有八个方向可以走,假设马的位置是(x,y)
     * 则有
     *      1. (x+1,y+2)
     *      2. (x+2,y+1)
     *      3. (x-1,y+2)
     *      4. (x-2,y+1)
     *      5. (x-2,y-1)
     *      6. (x-1,y-2)
     *      7. (x+1,y-2)
     *      8. (x+2,y-1)
     * */
    public static class Position {
        public int x;
        public int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void setX(int x) {
            this.x = x;
        }

        public void setY(int y) {
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof Position))return false;
            Position sec = (Position)obj;
            return (this.x==sec.x && this.y==sec.y);
        }
    }

    public static int getMethods(int mapX,int mapY,Position cur,Position aim,int steps){
        if(cur.x >= mapX || cur.x <0 || cur.y >= mapY || cur.y <0)return 0;
        if(steps==0){
            return cur.equals(aim) ? 1:0;
        }

        //if(cur.equals(aim))return 1;

        int pos1 = getMethods(mapX,mapY,new Position(cur.x+1,cur.y+2),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x+1,cur.y-2),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x-1,cur.y+2),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x-1,cur.y-2),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x+2,cur.y+1),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x+2,cur.y-1),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x-2,cur.y+1),aim,steps-1);
        pos1 += getMethods(mapX,mapY,new Position(cur.x-2,cur.y-1),aim,steps-1);

        return pos1;
    }
    /**
     * 另外一个方法,就是看成(a,b)->(0,0)
     *
     *
     * */
    public static int getMethods2(Integer mapX,Integer mapY,Position cur,int steps){
        if(cur.x >= mapX || cur.x <0 || cur.y >= mapY || cur.y <0)return 0;
        if(steps==0){
            return cur.y==0 && cur.x==0 ? 1:0;
        }

        //if(cur.y==0 && cur.x==0)return 1;

        int pos1 = getMethods2(mapX,mapY,new Position(cur.x+1,cur.y+2),steps-1);//
        pos1 += getMethods2(mapX,mapY,new Position(cur.x+1,cur.y-2),steps-1);
        pos1 += getMethods2(mapX,mapY,new Position(cur.x-1,cur.y+2),steps-1);//
        pos1 += getMethods2(mapX,mapY,new Position(cur.x-1,cur.y-2),steps-1);
        pos1 += getMethods2(mapX,mapY,new Position(cur.x+2,cur.y+1),steps-1);
        pos1 += getMethods2(mapX,mapY,new Position(cur.x+2,cur.y-1),steps-1);
        pos1 += getMethods2(mapX,mapY,new Position(cur.x-2,cur.y+1),steps-1);
        pos1 += getMethods2(mapX,mapY,new Position(cur.x-2,cur.y-1),steps-1);

        return pos1;
    }
    /**
     * 这个方法的DP表因为变量有三个,因此是三维的分别是 x , y , step,因此优化如下
     * */

    public static  int[][][] getDP(Integer mapX,Integer mapY,int steps){
        int [][][] dp = new int[mapX][mapY][steps + 1];
        /**
         *
         *         if(steps==0){
         *             return cur.y==0 && cur.x==0 ? 1:0;
         *         }
         * */
        dp[0][0][0] = 1;

        for (int step = 1; step <= steps; step++) {
            for (int x = 0; x < mapX; x++) {
                for (int y = 0; y < mapY; y++) {
                    dp[x][y][step] += getValue(dp,mapX,mapY,x-1,y+2,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x-1,y-2,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x+1,y+2,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x+1,y-2,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x-2,y+1,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x-2,y-1,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x+2,y+1,step-1);
                    dp[x][y][step] += getValue(dp,mapX,mapY,x+2,y-1,step-1);
                    //System.out.println(dp[x][y][step]);
                }
            }
//            System.out.println();
//            System.out.println("step:"+step);
//            for(int[] row : dp[step]){
//                System.out.println(Arrays.toString(row));
//            }
        }

        return dp;
    }
    public static int getValue(int[][][] dp,Integer mapX,Integer mapY, int row, int col, int step){
        if (row < 0 || row >= mapX || col < 0 || col >= mapY ) {
            return 0;
        }
        return dp[row][col][step];
    }

    /**
     * 一个棋盘N*M,有一个人的位置在(a,b)如果这个人出了棋盘
     * 就会死掉,活着的时候会随机前后左右的走K步
     * 问这个人死掉的概率是多少
     * */

    public static int getdeathCnt(Integer N,Integer M,Position Bob,int steps){
        if(Bob.x >= N || Bob.y >=M || Bob.x <0 || Bob.y <0)return 1;
        if(steps==0){
            return 0;
        }
        return
         getdeathCnt(N,M,new Position(Bob.x-1,Bob.y),steps-1)+
         getdeathCnt(N,M,new Position(Bob.x+1,Bob.y),steps-1)+
         getdeathCnt(N,M,new Position(Bob.x,Bob.y+1),steps-1)+
         getdeathCnt(N,M,new Position(Bob.x,Bob.y-1),steps-1);
    }
    public static int getliveCnt(Integer N,Integer M,Position Bob,int steps){
        if(Bob.x >= N || Bob.y >=M || Bob.x <0 || Bob.y <0)return 0;
        if(steps==0){
            return 1;
        }
        return
                getliveCnt(N,M,new Position(Bob.x-1,Bob.y),steps-1)+
                        getliveCnt(N,M,new Position(Bob.x+1,Bob.y),steps-1)+
                        getliveCnt(N,M,new Position(Bob.x,Bob.y+1),steps-1)+
                        getliveCnt(N,M,new Position(Bob.x,Bob.y-1),steps-1);
    }

    /**
     * 一个数组都是正数,元素代表面值,张数任意张,如果要组成某个面值,有多少中方法
     *
     * */
    //可以自由使用arr[index...]所有的面值
    //需要搞定的钱数是rest
    //返回找零的方法数
    public static int process(int[] arr, int index, int rest){
        if(index==arr.length){
            return rest==0?1:0;
        }
        //arr[index]0张1张...不要超过rest的钱数

        int ways = 0;
        for(int zhang=0;arr[index]*zhang<=rest;zhang++){
            ways += process(arr,index+1,rest-arr[index]*zhang);
        }
        return ways;
    }
    //O(N*aim^2)
    public static int makeMoneyDP(int[] arr,int aim){
        if(arr==null)return 0;
        int N  = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for (int index = N-1; index >=0; index--) {
            for (int rest = 0; rest <=aim; rest++) {
                int ways = 0;
                for(int zhang=0;arr[index]*zhang<=rest;zhang++){    //这个地方还有优化空间
                    ways += dp[index+1][rest-arr[index]*zhang];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }
    //O(N*aim)
    /**
     *          x1 ... x2
     * b1   b2  b3 ... b4
     *  x2 = b1+b2+b3+b4
     *  但是我们忽略了x1 = b3+b2+b1
     *  因此计算x2的时候直接用x1 + b4即可得出
     *
     * */
    public static int makeMoneyDP2(int[] arr,int aim){
        if(arr==null)return 0;
        int N  = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for (int index = N-1; index >=0; index--) {
            for (int rest = 0; rest <=aim; rest++) {
                dp[index][rest] = dp[index+1][rest];
                if(rest-arr[index]>=0)
                    dp[index][rest] +=dp[index][rest-arr[index]];
            }
        }
        return dp[0][aim];
    }


    public static int[] generateRandomBuff(int maxValue,int maxLen){
        int[] buff = new int[(int)(Math.random()*maxLen) + 1];
        for (int i = 0; i < buff.length; i++) {
            buff[i] =(int) (Math.random()*maxValue) +1;
        }
        return buff;
    }

    /**
     * 在写尝试方法的时候尽量写出来的尝试方法
     * 每个可变参数尽量是0维的,比如 int char 尽量避免数组
     * 可变参数少
     *
     * */
    public static void main(String[] args) {
//        System.out.println(getMethods(9, 10, new Position(0, 0), new Position(7, 7), 10));
//        System.out.println(getMethods2(9, 10, new Position(7, 7), 10));
//        int[][][] dp = getDP(9,10,10);
//        System.out.println(dp[7][7][10]);
//        System.out.println(getdeathCnt(5,5,new Position(2,2),5));
//        System.out.println(getliveCnt(5,5,new Position(2,2),5));
        int testTime = 50000;
        int maxVlaue = 100;
        int maxLen = 10;
        boolean flag = false;
        for (int i = 0; i < testTime; i++) {

            int[] in = generateRandomBuff(maxVlaue,maxLen);


            int aim = (int)(Math.random()*3*maxVlaue) + maxVlaue;
            System.out.println(i+"st\t"+"Waitting Test:"+Arrays.toString(in)+"\taim:"+aim);
            //System.out.println();
            int process = process(in, 0, aim);
            int i1 = makeMoneyDP(in, aim);
            int i2 = makeMoneyDP2(in, aim);
            System.out.println("process = " + process);
            System.out.println("i1 = " + i1);
            System.out.println("i2 = " + i2);
            if(process!=i1 || i1!= i2){
                System.out.println("failed");
                break;
            }
            System.out.println();
        }

    }
}
